import java.util.*;

class Solution {
    // 创建一个邻接表
    Map<Character, HashSet<Character>> edges = new HashMap<>();
    // 创建一个入度表
    Map<Character, Integer> in = new HashMap<>();
    boolean check = false;
    public String alienOrder(String[] words) {
        // 1. 初始化入度表
        for(String word : words){
            for(int i = 0; i < word.length(); i++){
                char ch = word.charAt(i);
                if(!in.containsKey(ch)){
                    in.put(ch, 0);
                }
            }
        }
        // 2. 建图 - 有向无环图
        int len = words.length;
        for(int i = 0; i < len - 1; i++){
            for(int j = i + 1; j < len; j++){
                // 将邻接关系添加到哈希表中
                add(words[i], words[j]);
                if(check){
                    return "";
                }
            }
        }
        // 3. 拓扑排序
        Queue<Character> queue = new LinkedList<>();
        //    把入度为0的字符放进队列中
        for(char ch : in.keySet()){
            if(in.get(ch) == 0){
                queue.offer(ch);
            }
        }
        StringBuilder ret = new StringBuilder();
        while(!queue.isEmpty()){
            char ch = queue.poll();
            ret.append(ch);
            // 删除边
            if(edges.containsKey(ch)){
                for(char c : edges.get(ch)){
                    int n = in.get(c);
                    in.put(c, --n);
                    if(n == 0){
                        queue.offer(c);
                    }
                }
            }
        }
        // 4. 判断结果
        for(char ch : in.keySet()){
            if(in.get(ch) != 0){
                return "";
            }
        }
        return ret.toString();
    }
    public void add(String s1, String s2){
        int len1 = s1.length();
        int len2 = s2.length();
        int len = Math.min(len1, len2);
        int i = 0;
        while(i < len){
            char ch1 = s1.charAt(i);
            char ch2 = s2.charAt(i);
            if(ch1 == ch2){
                i++;
            }else{
                // 添加邻接关系
                if(!edges.containsKey(ch1)){
                    edges.put(ch1, new HashSet<Character>());
                }
                if(!edges.get(ch1).contains(ch2)){
                    edges.get(ch1).add(ch2);
                    in.put(ch2, in.get(ch2) + 1);
                }
                break;
            }
        }
        if(i < len1 && i >= len2){
            check = true;
        }
    }
}